package jzOffer;

/**
 * @author 郝文雪
 * @date 2022/8/2 17:37
 * @Description Test
 */
public class JZ12 {
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        int n=matrix.length;
        int m=matrix[0].length;
        boolean flag=false;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]==word.charAt(0)){
                    if(dfs(matrix,word,i,j,0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] matrix, String word,int i,int j,int k){
        if(i<0 || j<0 || i>=matrix.length || j>=matrix[0].length || matrix[i][j]=='*'|| matrix[i][j]!=word.charAt(k)){
            return false;
        }
        if(k==word.length()-1){
            return true;
        }
        matrix[i][j]='*';
        if(dfs(matrix,word,i+1,j,k+1)||
                dfs(matrix,word,i,j+1,k+1)||
                dfs(matrix,word,i-1,j,k+1)||
                dfs(matrix,word,i,j-1,k+1)){
            return true;
        }
        matrix[i][j]=word.charAt(k);
        return false;

    }
}
